/******************************************************************************
	Cobalt - utility libraries for building XNA games
	Copyright (C) 2008 Philip Djonov

	This program is free software; you can redistribute it and/or modify it
	under the terms of the GNU General Public License as published by the Free
	Software Foundation; either version 2 of the License, or (at your option)
	any later version.

	This program is distributed in the hope that it will be useful, but
	WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
	or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
	for more details.

	You should have received a copy of the GNU General Public License along
	with this program; if not, write to the
	
		Free Software Foundation, Inc.
		51 Franklin Street, Fifth Floor
		Boston, MA  02110-1301, USA.
******************************************************************************/

using System;
using System.Collections.Generic;
using System.IO;

using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.Graphics;

namespace Cobalt.Framework.Bsp
{

	partial class BspData
	{

		public sealed class Trace
		{
			private BspData owner;
			internal Trace( BspData owner )
			{
				this.owner = owner;

				brushCheckMask = new uint[owner.brushes.Length / 32 + 1];
			}

			public BspData Owner
			{
				get { return owner; }
			}

			private BrushContents contentMask;
			/// <summary>
			/// Gets or sets the collision contents mask.
			/// </summary>
			public BrushContents ContentMask
			{
				get { return contentMask; }
				set { contentMask = value; }
			}

			private Vector3 boxOffset, boxExtents;
			private BoundingBox traceBox;

			public BoundingBox TraceBox
			{
				get { return new BoundingBox( traceBox.Min + boxOffset, traceBox.Max + boxOffset ); }
				set
				{
					boxOffset = (value.Min + value.Max) * 0.5F;
					traceBox = new BoundingBox( value.Min - boxOffset, value.Max - boxOffset );
					boxExtents = Vector3.Max( -traceBox.Min, traceBox.Max );					
				}
			}

			public enum TraceType
			{
				Ray,
				Box,
			}

			private TraceType type;
			public TraceType Type
			{
				get { return type; }
				set { type = value; }
			}

			//computed during the trace
			private float traceLength;
			private float hitFrac, hitDist;
			private bool startsSolid, allSolid;
			private int hitSurfaceFlags; //valid iff there is a hit
			private BrushContents hitContentFlags; //valid iff there is a hit
			private Plane hitPlane; //valid iff there is a hit

			private Vector3 traceStart, traceEnd;

			//computed after tracing
			private Vector3 hitPoint;

			public float HitFraction { get { return hitFrac; } }
			public float HitDistance { get { return hitDist; } }
			public bool HasHit { get { return hitFrac < 1.0F; } }
			public Vector3 HitPoint { get { return hitPoint; } }
			public Plane HitPlane { get { return hitPlane; } }
			public bool StartsSolid { get { return startsSolid; } }
			public bool AllSolid { get { return allSolid; } }

			public bool TraceRay( Vector3 start, Vector3 end )
			{
				SetupTrace( ref start, ref end );
				TraceThroughNode( owner.partitions[0], 0, 1, ref start, ref end );
				return EndTrace( ref start, ref end );
			}

			private void SetupTrace( ref Vector3 start, ref Vector3 end )
			{
				if( type == TraceType.Box )
				{
					start += boxOffset;
					end += boxOffset;
				}

				traceStart = start;
				traceEnd = end;

				startsSolid = false;
				allSolid = false;
				hitFrac = 1.0F;
				
				Vector3.Distance( ref start, ref end, out traceLength );
				hitDist = traceLength;

				Array.Clear( brushCheckMask, 0, brushCheckMask.Length );
			}

			private bool EndTrace( ref Vector3 start, ref Vector3 end )
			{
				if( hitFrac == 1.0F )
				{
					hitPoint = end;
					hitDist = traceLength;
					return false;
				}
				else
				{
					Vector3.Lerp( ref start, ref end, hitFrac, out hitPoint );
					hitDist = traceLength * hitFrac;
					return true;
				}
			}

			private const float Epsilon = 0.125F;
			private uint[] brushCheckMask;

			private void TraceThroughBrush( Brush brush, ref Vector3 start, ref Vector3 end )
			{
				float startFrac = -1.0F;
				float endFrac = 1.0F;

				bool startsOut = false;
				bool endsOut = false;

				BrushSide clipSide = null;

				foreach( BrushSide side in brush.Sides )
				{
					float sd, ed;

					switch( type )
					{
						case TraceType.Box:
							{
								Vector3 offset = new Vector3(
									side.plane.Normal.X < 0 ? traceBox.Max.X : traceBox.Min.X,
									side.plane.Normal.Y < 0 ? traceBox.Max.Y : traceBox.Min.Y,
									side.plane.Normal.Z < 0 ? traceBox.Max.Z : traceBox.Min.Z );
								
								float dist;
								Vector3.Dot( ref offset, ref side.plane.Normal, out dist );

								sd = side.Plane.DotCoordinate( start ) + dist;
								ed = side.Plane.DotCoordinate( end ) + dist;
							}
							break;

						case TraceType.Ray:
						default:
							side.Plane.DotCoordinate( ref start, out sd );
							side.Plane.DotCoordinate( ref end, out ed );
							break;
					}

					if( sd > 0 )
						startsOut = true;
					if( ed > 0 )
						endsOut = true;

					if( sd > 0 && (ed >= Epsilon || ed >= sd) )
						//both endpoints are outside the brush
						return;

					if( sd <= 0 && ed <= 0 )
						continue;

					if( sd > ed )
					{
						float frac = (sd - Epsilon) / (sd - ed);
						if( frac > startFrac )
						{
							startFrac = frac;
							clipSide = side;
						}
					}
					else
					{
						float frac = (sd + Epsilon) / (sd - ed);
						if( frac < endFrac )
							endFrac = frac;
					}
				}

				if( !startsOut )
				{
					startsSolid = true;
					if( !endsOut )
					{
						allSolid = true;
						hitFrac = 0;
						hitContentFlags = brush.ContentFlags;
						hitSurfaceFlags = 0;
					}

					return;
				}

				if( startFrac < endFrac && startFrac > -1.0F && startFrac < hitFrac )
				{
					if( startFrac < 0 )
						startFrac = 0;

					hitFrac = startFrac;

					hitPlane = clipSide.Plane;
					hitSurfaceFlags = clipSide.SurfaceFlags;
					hitContentFlags = brush.ContentFlags;
				}
			}

			private void TraceThroughLeaf( LeafNode leaf, ref Vector3 start, ref Vector3 end )
			{
				foreach( Brush brush in leaf.Brushes )
				{
					if( brush.Sides.Length == 0 ||
						(brush.ContentFlags & contentMask) == BrushContents.None ||
						(brushCheckMask[brush.brushIndex >> 5] & (1U << (brush.brushIndex & 0x1F))) != 0 )
						continue;

					TraceThroughBrush( brush, ref start, ref end );

					brushCheckMask[brush.brushIndex >> 5] |= 1U << (brush.brushIndex & 0x1F);

					if( hitFrac == 0.0F )
						//we hit right away, no point going further
						return;
				}
			}

			private void TraceThroughNode( Node node, float startFrac, float endFrac,
				ref Vector3 start, ref Vector3 end )
			{
			retrace:
				LeafNode leaf = node as LeafNode;
				if( leaf != null )
				{
					TraceThroughLeaf( leaf, ref traceStart, ref traceEnd );
					return;
				}

				PartitionNode part = node as PartitionNode;

				float sd, ed;

				part.plane.DotCoordinate( ref start, out sd );
				part.plane.DotCoordinate( ref end, out ed );

				float offset;
				switch( type )
				{
					case TraceType.Box:
						offset =
							Math.Abs( boxExtents.X * part.plane.Normal.X ) +
							Math.Abs( boxExtents.Y * part.plane.Normal.Y ) +
							Math.Abs( boxExtents.Z * part.plane.Normal.Z );

						//offset = 2048;
						break;

					case TraceType.Ray:
					default:
						offset = 0;
						break;
				}

				if( sd >= offset && ed >= offset )
				{
					node = part.child0;
					goto retrace;
				}

				if( sd < -offset && ed < -offset )
				{
					node = part.child1;
					goto retrace;
				}

				//line spans the plane, trace both sides
				bool frontFirst;
				float frac1, frac2, midFrac;
				Vector3 midPoint;

				if( sd < ed )
				{
					frontFirst = false;
					
					float invDist = 1.0F / (sd - ed);

					frac1 = (sd - offset + Epsilon) * invDist;
					frac2 = (sd + offset + Epsilon) * invDist;
				}
				else if( ed < sd )
				{
					frontFirst = true;

					float invDist = 1.0F / (sd - ed);

					frac1 = (sd + offset + Epsilon) * invDist;
					frac2 = (sd - offset - Epsilon) * invDist;
				}
				else
				{
					frontFirst = true;
					frac1 = 1.0F;
					frac2 = 0.0F;
				}

				if( frac1 < 0.0F )
					frac1 = 0.0F;
				else if( frac1 > 1.0F )
					frac1 = 1.0F;

				if( frac2 < 0.0F )
					frac2 = 0.0F;
				else if( frac2 > 1.0F )
					frac2 = 1.0F;

				midFrac = startFrac + (endFrac - startFrac) * frac1;
				Vector3.Lerp( ref start, ref end, midFrac, out midPoint );

				TraceThroughNode( frontFirst ? part.child0 : part.child1, startFrac, midFrac, ref start, ref midPoint );

				midFrac = startFrac + (endFrac - startFrac) * frac2;
				Vector3.Lerp( ref start, ref end, midFrac, out midPoint );

				TraceThroughNode( frontFirst ? part.child1 : part.child0, midFrac, endFrac, ref midPoint, ref end );
			}
		}

		public Trace CreateTrace()
		{
			if( partitions.Length == 0 )
				throw new InvalidOperationException( "No collision data has been loaded." );

			return new Trace( this );
		}
	}

}